package cn.kingshion.linkedlist;

import java.util.Stack;

public class SingleLinkedListDemo {
    public static void main(String[] args) {

        //先定义多个节点，用来存放数据
        Node node1 = new Node(1, "jjx", "jjx");
        Node node2 = new Node(2, "kingshion", "kingshion");
        Node node3 = new Node(3, "ysy", "ysy");
        Node node4 = new Node(4, "yisiyuan", "yisiyuan");
        Node node5 = new Node(5, "jxy", "jxy");
        Node node6 = new Node(6, "jinxiangyu", "jinxiangyu");

        //定义一个链表用来管理节点
        SingleLinkedList singleLinkedList = new SingleLinkedList();

        //测试不论顺序的加入链表
//        singleLinkedList.add(node1);
//        singleLinkedList.add(node2);
//        singleLinkedList.add(node3);
//        singleLinkedList.add(node4);
//        singleLinkedList.add(node5);
//        singleLinkedList.add(node6);

        //测试按顺序加入链表
        //若新增的节点已经存在了链表中，则插入失败，返回提示信息
        singleLinkedList.addByOrder(node1);
        singleLinkedList.addByOrder(node2);
        singleLinkedList.addByOrder(node3);
//        singleLinkedList.addByOrder(node3);
        singleLinkedList.addByOrder(node4);
        singleLinkedList.addByOrder(node5);
        singleLinkedList.addByOrder(node6);
//        singleLinkedList.addByOrder(node6);

        //输出
        System.out.println("更新前的链表。。。");
        //打印输出更新之前的链表
        singleLinkedList.list();

        //测试反转后的链表  栈实现  reversePrint  「百度面试题」
        System.out.println();
        System.out.println("反转链表，栈实现");
        SingleLinkedList.reversePrint(singleLinkedList.head);
        System.out.println();


        //测试反转链表  reverse    「腾讯面试题」
        System.out.println();
        System.out.println("反转之后的链表。。。");
        SingleLinkedList.reverseLinkedList(singleLinkedList.head);
        singleLinkedList.list();//输出反转后的链表
        System.out.println();

        //测试更新链表的数据
        System.out.println("更新后的链表。。。");
        Node newNode = new Node(1, "小金", "金江璇");
        singleLinkedList.update(newNode);
        //打印输出更新之后的链表
        singleLinkedList.list();
        System.out.println();

        //测试删除链表的节点
        System.out.println("删除后的链表。。。");
        singleLinkedList.delete(6);
        singleLinkedList.delete(6);         //再次删除已经不存在的节点
        singleLinkedList.list();
        System.out.println();


        //测试新浪面试题
        System.out.println("新浪面试题：");
        System.out.println("在链表中查找一个倒数第K个节点：");
        System.out.println("链表的长度为 ： " + SingleLinkedList.getLenth(singleLinkedList.head));
        System.out.println("倒数第3个节点是 ： " + SingleLinkedList.findLastIndexNode(singleLinkedList.head, 3));


    }
}


/**
 * 定义一个链表，用来管理这些节点     把节点连接在一起
 */
class SingleLinkedList {
    //先初始化一个头结点   head
    Node head = new Node(0, "", "");

    /**
     * 从尾到头打印单链表 【百度面试题     要求方式 ：Stack栈】
     */
    public static void reversePrint(Node head) {
        if (head.next == null) {
            System.out.println("空链表，不能打印。。。。");
        }
        Node cur = head.next;
        //创建一个 Stack 栈， 用来存储遍历的数据
        Stack<Node> stack = new Stack<Node>();
        //入栈
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        //出栈
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }


    /**
     * 单链表的反转【腾讯面试题，有点难度】
     */
    public static void reverseLinkedList(Node head) {
        //如果当前链表为空，或者只有一个节点，那么直接返回，无需反转
        if (head.next == null || head.next.next == null) {
            System.out.println("链表为空，无法反转。");
            return;
        }
        //定义辅助指针（变量） 用来帮助我们
        Node cur = head.next;
        //指向当前节点  cur 的下一个节点
        Node next = null;
        //定义一个反转的头结点
        Node reverseHead = new Node(0, "", "");

        while (cur != null) {
            next = cur.next;        // 先暂时保存当前节点的下一个节点， 后面要用
            cur.next = reverseHead.next;        //将当前节点的下一个节点指向反转后新链表的头节点
            reverseHead.next = cur;         //将 cur 连接到新的反转链表
            cur = next;         //让 cur 后移
        }
        head.next = reverseHead.next;

    }

    /**
     * 【新浪面试题】
     * 1、求单链表中有效节点的个数
     * 思路：直接遍历，但是要考虑一个问题就是 ：
     * 原链表中是否有头结点，如果存在的话是需要舍弃的，头结点是一个无效节点
     */
    public static int getLenth(Node head) {
        if (head.next == null) {
            return 0;
        }
        Node temp = head.next;
        //定义一个变量用来存储节点数量
        int lenth = 0;
        while (temp != null) {
            lenth++;
            temp = temp.next;
        }
        return lenth;
    }

    /**
     * 【新浪面试题】
     * 2、查找单链表中的倒数第k个结点
     * 调用第 1 题的结果进行运算
     * 思路：先做一遍历得到整个链表的 size 大小
     * 然后再做一个遍历，要知道求倒数第几个其实就是求正数的第 （size - index）个节点
     * 在第二遍遍历之前要验证 index 的合法性
     */
    public static Node findLastIndexNode(Node head, int index) {
        if (head.next == null) {
            return null;
        }
        int count = getLenth(head);
        if (index <= 0 || index > count) {
            System.out.println("查找的数据超出链表范围。");
            return null;
        }
        Node res = head.next;
        for (int i = 0; i < count - index; i++) {
            res = res.next;
        }
        return res;

    }


    /**
     * 添加节点到单向链表中，
     * 思路：当不考虑节点编号时候，     先找到最后一个节点， 然后将最后一个节点的 next  指向要添加的新节点。
     *
     * @param node
     */
    public void add(Node node) {
        //因为头结点是不能随意变动的，所以定义一个临时变量节点，用来对链表进行遍历，找到链表最后的一个节点。
        Node temp = head;

        while (true) {
            if (temp.next == null) {
                break;
            }
            //如果目前的节点不是最后一个的话，那么就向后递推
            temp = temp.next;
        }

        //当退出循环后，表明已经找到了最后一个节点，这个时候只要将新的节点添加到最后的节点后面就可以了。
        temp.next = node;
    }


    /**
     * 按编号 顺序 添加节点
     *
     * @param node
     */
    public void addByOrder(Node node) {
        //因为头结点是不能随意变动的，所以定义一个临时变量节点，用来对链表进行遍历，找到链表最后的一个节点。
        Node temp = head;
        //定义一个标志，用来标志是否存在跟插入节点的同样的节点
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                //若已经到达链表的最后节点，没有找到也同样返回
                break;
            }
            if (temp.next.no > node.no) {
                //说明已经找到了，应该插入的位置，插入位置应个事temp的下一个位置，所以采用使用  temp.next.no
                break;
            } else if (temp.next.no == node.no) {
                //如果已经存在了一个这样的节点，那么将标志位改变
                flag = true;
                break;
            }
            //将指针向后移动，遍历整个链表
            temp = temp.next;
        }
        if (flag) {
            System.out.println("已经存在一个no为 " + node.no + " 的节点");
        } else {
            //链表的插入过程
            node.next = temp.next;
            temp.next = node;
        }
    }

    /**
     * 更新节点的信息
     * 根据新节点的 no 来查找链表中的节点，然后进行修改
     *
     * @param newNode
     */
    public void update(Node newNode) {
        //如果链表为空则无法修改
        if (head.next == null) {
            System.out.println("链表为空，无法修改");
        }
        //
        Node temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == newNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = newNode.name;
            temp.nikename = newNode.nikename;
        } else {
            System.out.println("没有找到节点 " + newNode.no + " 的节点");
            return;
        }
    }

    /**
     * 删除一个节点
     *
     * @param no
     */
    public void delete(int no) {
        Node temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                //已经到达链表的最后
                break;
            }
            if (temp.next.no == no) {
                //说明已经找到了
                flag = true;
                break;
            }
            //没有找到继续向后遍历链表
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.println("要删除的节点 " + no + " 不存在");
        }


    }


    /**
     * 打印链表
     */
    public void list() {
        if (head.next == null) {
            System.out.println("链表为空！");
            return;
        }
        //head 头节点是不能随意的改变位置的。所以任然定义一个临时变量来进行遍历
        Node temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            //先输出节点信息，
            System.out.println(temp);
            //然后让节点向后移动
            temp = temp.next;
        }
    }
}


/**
 * 定义节点，链表就是由许多个不同的节点连接在一起的
 */
class Node {
    public int no;
    public String name;
    public String nikename;
    public Node next;       //指向下一个节点

    //构造器
    public Node(int no, String name, String nikename) {
        this.no = no;
        this.name = name;
        this.nikename = nikename;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nikenaem='" + nikename + '\'' +
                '}';
    }
}
